//原文链接
//https://blog.csdn.net/ITSOK_123/article/details/124614396
//前序遍历
//递归（O(N),O(N)）
void preorderTraverse(Node* root,vector<int>& ivec){
        if(root == nullptr) return;
        ivec.push_back(root->val);
        for(Node *cur : root->children){
            preorderTraverse(cur,ivec);
        }
    }
    vector<int> preorder(Node* root) {
        vector<int> ivec;
        preorderTraverse(root,ivec);
        return ivec;
    }
//迭代（O(N),O(N)）

vector<int> preorder(Node* root) {
        vector<int> ivec;
        stack<Node*> st;
        if(root == nullptr)  return ivec;
        // 保存当前节点的子节点访问记录
        unordered_map<Node*,int> mni;
        Node* node = root;
        while(!st.empty() || node){
            while(node){
                ivec.emplace_back(node->val);
                st.push(node);
                // 只有当前节点有着子节点才能进行访问
                if(node->children.size()>0){
                    mni[node]=0;
                   node = node->children[0]; 
                } 
                else node = nullptr;
            }
            // 读取栈顶元素并操作
            node = st.top();
            // 获取上次访问此节点的子节点下标
            int index = mni.count(node)>0 ?mni[node]:-1;
            index+=1;
            // 如果子节点未访问完
            if(index < node->children.size()){
                mni[node]=index;
                node = node->children[index];
            }else{
            //若节点的子节点已经访问完，弹出此节点
                st.pop();
                mni.erase(node);
                node = nullptr;
            }
        }
        return ivec;
    }
//优化的迭代法（O(N),O(N)）
vector<int> preorder(Node* root) {
        vector<int> ivec;
        stack<Node*> st;
        if(root == nullptr)  return ivec;
        Node* node = root;
        st.push(node);
        //栈不为空则弹出并处理
        while(!st.empty()){
            node = st.top();
            st.pop();
            ivec.emplace_back(node->val);
            // 逆序压入栈，弹出处理的时候就是从左到右
            for(auto it = node->children.rbegin();it!=node->children.rend();it++){
                st.push(*it);
            }      
        }
        return ivec;
    }

//后序遍历
//后续递归（O(N),O(N)）
void postTraverse(Node* root,vector<int> &iv){
        if(root == nullptr) return;
        // 先遍历子节点，再遍历父节点
        for(int i=0;i<root->children.size();i++){
            postTraverse(root->children[i],iv);
        }
        iv.emplace_back(root->val);
    }
    vector<int> postorder(Node* root) {
        vector<int>ivec;
        postTraverse(root,ivec);
        return ivec;
    }

//后序迭代（O(N),O(N)）
vector<int> postorder(Node* root) {
        vector<int>ivec;
        stack<Node*>st;
        if(root == nullptr) return ivec;
        Node *node = root;
        // 子节点访问记录标记
        unordered_map<Node*,int> mni;
        while(!st.empty() || node){
            //最左边下沉
            while(node){
                st.emplace(node);
                //若当前节点有子节点
                if(node->children.size() > 0){
                    mni[node] = 0;
                    node = node->children[0];
                }else{
                    node = nullptr;
                }
            }
            node = st.top();
            int index = mni.count(node)>0 ? mni[node]:-1;
            index+=1;
            if(index<node->children.size()){
                mni[node] = index;
                node = node->children[index];
            }else{
                // 元素出栈之前才能压入数组，
                // 出栈说明其子节点刚刚都访问完
                ivec.emplace_back(node->val);
                st.pop();
                mni.erase(node);
                node = nullptr;
            }
        }
        return ivec;
    }